{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Interval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeInterval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>实数集合可以表示为若干不相交区间的并集，其中每个区间的形式为 <code>[a, b)</code>（左闭右开），表示满足&nbsp;<code>a &lt;= x &lt; b</code> 的所有实数&nbsp; <code>x</code>&nbsp;的集合。如果某个区间&nbsp;<code>[a, b)</code> 中包含实数 <code>x</code> ，则称实数 <code>x</code> 在集合中。</p>\n",
    "\n",
    "<p>给你一个 <strong>有序的</strong> 不相交区间列表 <code>intervals</code>&nbsp;。<code>intervals</code> 表示一个实数集合，其中每一项 <code>intervals[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 都表示一个区间 <code>[a<sub>i</sub>, b<sub>i</sub>)</code> 。再给你一个要删除的区间 <code>toBeRemoved</code> 。</p>\n",
    "\n",
    "<p>返回 <em>一组实数，该实数表示<code>intervals</code> 中&nbsp;<strong>删除</strong>&nbsp;了 <code>toBeRemoved</code> 的部分</em>&nbsp;。<em>换句话说，返回实数集合，并满足集合中的每个实数 <code>x</code> 都在&nbsp;<code>intervals</code> 中，但不在 <code>toBeRemoved</code> 中。你的答案应该是一个如上所述的 <strong>有序的</strong> 不相连的间隔列表&nbsp;。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/24/removeintervalex1.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]\n",
    "<strong>输出：</strong>[[0,1],[6,7]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/24/removeintervalex2.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[0,5]], toBeRemoved = [2,3]\n",
    "<strong>输出：</strong>[[0,2],[3,5]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]\n",
    "<strong>输出：</strong>[[-5,-4],[-3,-2],[4,5],[8,9]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= intervals.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= a<sub>i</sub> &lt; b<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-interval](https://leetcode.cn/problems/remove-interval/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-interval](https://leetcode.cn/problems/remove-interval/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,2],[3,4],[5,7]]\\n[1,6]', '[[0,5]]\\n[2,3]', '[[-5,-4],[-3,-2],[1,2],[3,5],[8,9]]\\n[-1,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        idx = 0\n",
    "        while idx < len(intervals):\n",
    "            if intervals[idx][0] >= toBeRemoved[0] and intervals[idx][1] <= toBeRemoved[1]:\n",
    "                intervals.pop(idx)\n",
    "                continue\n",
    "            if toBeRemoved[0]>=intervals[idx][1]:\n",
    "                idx += 1\n",
    "                continue\n",
    "            if toBeRemoved[1] <= intervals[idx][0]:\n",
    "                break\n",
    "            if intervals[idx][0] < toBeRemoved[0] and intervals[idx][1] < toBeRemoved[1]:\n",
    "                intervals[idx][1] = toBeRemoved[0]\n",
    "                idx += 1\n",
    "                continue\n",
    "            if intervals[idx][0] > toBeRemoved[0] and intervals[idx][1] > toBeRemoved[0]:\n",
    "                intervals[idx][0] = toBeRemoved[1]\n",
    "                idx += 1\n",
    "                continue\n",
    "            else:\n",
    "                tmp = intervals[idx][1]\n",
    "                if intervals[idx][0] == toBeRemoved[0]:\n",
    "                    intervals[idx][0] = toBeRemoved[1]\n",
    "                    idx += 1\n",
    "                    continue\n",
    "                if intervals[idx][1] == toBeRemoved[1]:\n",
    "                    intervals[idx][1] = toBeRemoved[0]\n",
    "                    idx += 1\n",
    "                    continue\n",
    "                intervals[idx][1] = toBeRemoved[0]\n",
    "                intervals.insert(idx+1,[toBeRemoved[1],tmp])\n",
    "                idx += 2\n",
    "\n",
    "                continue\n",
    "        return intervals\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        left, right = toBeRemoved\n",
    "        res = []\n",
    "        for interval in intervals:\n",
    "            if interval[1]<=left or interval[0]>=right:\n",
    "                res.append(interval)\n",
    "            else:\n",
    "                if interval[0]<left:\n",
    "                    res.append([interval[0],left])\n",
    "                if interval[1]>right:\n",
    "                    res.append([right,interval[1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        for i in intervals:\n",
    "            if i[0] >= toBeRemoved[0] and i[1] <= toBeRemoved[1]:\n",
    "                continue\n",
    "            elif i[0] <= toBeRemoved[0] and i[1] >= toBeRemoved[1]:\n",
    "                if i[0] != toBeRemoved[0]:\n",
    "                    res.append([i[0], toBeRemoved[0]])\n",
    "                if i[1] != toBeRemoved[1]:\n",
    "                    res.append([toBeRemoved[1], i[1]])\n",
    "            elif i[0] >= toBeRemoved[1] or i[1] <= toBeRemoved[0]:\n",
    "                res.append(i)\n",
    "            elif i[0] < toBeRemoved[0] < i[1] <=toBeRemoved[1]:\n",
    "                res.append([i[0], toBeRemoved[0]])\n",
    "            elif toBeRemoved[0] < i[0] <toBeRemoved[1] <= i[1]:\n",
    "                res.append([toBeRemoved[1], i[1]])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        n = len(intervals)\n",
    "        lt, rt = 0, n - 1\n",
    "\n",
    "        while rt >= lt:\n",
    "            mid = (lt + rt)//2\n",
    "            if intervals[mid][1] <= toBeRemoved[0]:\n",
    "                lt = mid + 1\n",
    "            else:\n",
    "                rt = mid - 1\n",
    "\n",
    "        ans = intervals[:lt]\n",
    "\n",
    "        if intervals[lt][0] < toBeRemoved[0]:\n",
    "            ans.append([intervals[lt][0], toBeRemoved[0]])\n",
    "        \n",
    "        rt = n - 1\n",
    "\n",
    "        while rt >= lt:\n",
    "            mid = (lt + rt)//2\n",
    "            if intervals[mid][0] <= toBeRemoved[1]:\n",
    "                lt = mid + 1\n",
    "            else:\n",
    "                rt = mid - 1\n",
    "        \n",
    "        if intervals[rt][1] > toBeRemoved[1]:\n",
    "            ans.append([toBeRemoved[1], intervals[rt][1]])\n",
    "        \n",
    "        return ans + intervals[rt + 1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        n = len(intervals)\n",
    "        res = []\n",
    "        for x in intervals:\n",
    "            if x[1] <= toBeRemoved[0] or x[0] >= toBeRemoved[1]:\n",
    "                res.append(x)\n",
    "                continue\n",
    "            if x[0] < toBeRemoved[0]:\n",
    "                res.append([x[0], toBeRemoved[0]])\n",
    "            if x[1] > toBeRemoved[1]:\n",
    "                res.append([toBeRemoved[1], x[1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for interval in intervals:\n",
    "            # 不相交\n",
    "            if toBeRemoved[1] < interval[0] or toBeRemoved[0] >= interval[1]:\n",
    "                ans.append(interval)\n",
    "                continue\n",
    "            # 相交\n",
    "            if interval[0] < toBeRemoved[0]:\n",
    "                ans.append([interval[0], toBeRemoved[0]])\n",
    "            if interval[1] > toBeRemoved[1]:\n",
    "                ans.append([toBeRemoved[1], interval[1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for interval in intervals:\n",
    "            if interval[1] <= toBeRemoved[0] or interval[0] >= toBeRemoved[1]:\n",
    "                res.append(interval)\n",
    "                continue\n",
    "            if interval[0] < toBeRemoved[0]:\n",
    "                res.append([interval[0], toBeRemoved[0]])\n",
    "            if interval[1] > toBeRemoved[1]:\n",
    "                res.append([toBeRemoved[1], interval[1]])\n",
    "        return res\n",
    "\n",
    "\n",
    "        # remove_start, remove_end = toBeRemoved\n",
    "        # output = []\n",
    "\n",
    "        # for start, end in intervals:\n",
    "        #     # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "        #     if start > remove_end or end < remove_start:\n",
    "        #         output.append([start, end])\n",
    "        #     else:\n",
    "        #         # 需要保留左区间吗？\n",
    "        #         if start < remove_start:\n",
    "        #             output.append([start, remove_start])\n",
    "        #         # 需要保留右区间吗？\n",
    "        #         if end > remove_end:\n",
    "        #             output.append([remove_end, end])\n",
    "\n",
    "        # return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for interval in intervals:\n",
    "            if interval[1] <= toBeRemoved[0] or interval[0] >= toBeRemoved[1]:\n",
    "                res.append(interval)\n",
    "            else:\n",
    "                if interval[0] < toBeRemoved[0]:\n",
    "                    res.append([interval[0], toBeRemoved[0]])\n",
    "                if interval[1] > toBeRemoved[1]:\n",
    "                    res.append([toBeRemoved[1], interval[1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        n = len(intervals)\n",
    "        ans = []\n",
    "        for i in range(len(intervals)):\n",
    "            if intervals[i][0] >= toBeRemoved[-1] or intervals[i][-1] <= toBeRemoved[0]:\n",
    "                ans.append(intervals[i])\n",
    "            else:\n",
    "                if intervals[i][0] < toBeRemoved[0]:\n",
    "                    ans.append([intervals[i][0], toBeRemoved[0]])\n",
    "                if intervals[i][-1] > toBeRemoved[-1]:\n",
    "                    ans.append([toBeRemoved[-1], intervals[i][-1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        delList = []\n",
    "        appendList = []\n",
    "        for i in range(len(intervals)):\n",
    "            if intervals[i][0] > toBeRemoved[1] or intervals[i][1] < toBeRemoved[0]:\n",
    "                continue\n",
    "            if intervals[i][0] < toBeRemoved[0] and intervals[i][1] <= toBeRemoved[1]:\n",
    "                print(intervals[i])\n",
    "                intervals[i] = [intervals[i][0], toBeRemoved[0]]\n",
    "                print(intervals[i])\n",
    "            if intervals[i][0] >= toBeRemoved[0] and intervals[i][1] > toBeRemoved[1]:\n",
    "                intervals[i] = [toBeRemoved[1], intervals[i][1]]\n",
    "            if intervals[i][0] < toBeRemoved[0] and intervals[i][1] > toBeRemoved[1]:\n",
    "                appendList.append([toBeRemoved[1], intervals[i][1]])\n",
    "                intervals[i] = [intervals[i][0], toBeRemoved[0]]\n",
    "            if intervals[i][0] >= toBeRemoved[0] and intervals[i][1] <= toBeRemoved[1]:\n",
    "                delList.append(intervals[i])\n",
    "        for i in delList:\n",
    "            intervals.remove(i)\n",
    "        for i in appendList:\n",
    "            intervals.append(i)\n",
    "        intervals.sort(key = lambda x: x[0])\n",
    "        return intervals\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        result=[]\n",
    "        for i,interval in enumerate(intervals):\n",
    "            if interval[0]>=toBeRemoved[0] and interval[1]<=toBeRemoved[1]:\n",
    "                continue\n",
    "            elif toBeRemoved[0]>interval[0] and toBeRemoved[0]<interval[1]:\n",
    "                result.append([intervals[i][0],toBeRemoved[0]])\n",
    "                if interval[1]>toBeRemoved[1]:\n",
    "                    result.append([toBeRemoved[1],interval[1]])\n",
    "            elif interval[0]<toBeRemoved[1] and toBeRemoved[1]<=interval[1]:\n",
    "                # print(interval)\n",
    "                result.append([toBeRemoved[1],interval[1]])\n",
    "            else:\n",
    "                result.append(interval)\n",
    "                # continue\n",
    "        return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        lis,mark=[],True\n",
    "        mark2,mark3,mark4=True,True,True\n",
    "        if intervals[0]==toBeRemoved:\n",
    "            return []\n",
    "        for i in intervals:\n",
    "            if toBeRemoved[0]<=i[1] and toBeRemoved[0]>=i[0]:\n",
    "                if i[0]!=toBeRemoved[0]:\n",
    "                    lis.append([i[0],toBeRemoved[0]])\n",
    "                    mark=False\n",
    "            if mark2:\n",
    "                if not toBeRemoved[0]>i[1]:\n",
    "                    mark=False\n",
    "                    mark2=False\n",
    "            if mark:    \n",
    "                lis.append(i)\n",
    "            if toBeRemoved[1]<=i[1] and toBeRemoved[1]>=i[0]:\n",
    "                if toBeRemoved[1]!=i[1]:\n",
    "                    lis.append([toBeRemoved[1],i[1]])\n",
    "                mark=True\n",
    "                mark4=False\n",
    "            if mark3:\n",
    "                if not toBeRemoved[1]>i[0] and mark4:\n",
    "                    lis.append(i)\n",
    "                    mark=True\n",
    "                    mark3=False\n",
    "        return lis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        ts, te = toBeRemoved\n",
    "        for itv in intervals:\n",
    "            s, e = itv\n",
    "            if e <= ts or s >= te:\n",
    "                res.append(itv)\n",
    "                continue\n",
    "            if ts <= s < te and ts < e <= te:\n",
    "                continue\n",
    "            if s < ts < e:\n",
    "                res.append([s, ts])\n",
    "            if s < te < e:\n",
    "                res.append([te, e])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        counter = 0\n",
    "        while counter < len(intervals):\n",
    "            interval = intervals[counter]\n",
    "            if interval[1] <= toBeRemoved[0] or interval[0] >= toBeRemoved[1]:\n",
    "                res.append(interval)\n",
    "            elif interval[0] < toBeRemoved[0]:\n",
    "                if interval[1] > toBeRemoved[0] and interval[1] <= toBeRemoved[1]:\n",
    "                    res.append([interval[0], toBeRemoved[0]])\n",
    "                elif interval[1] > toBeRemoved[1]:\n",
    "                    res.append([interval[0], toBeRemoved[0]])\n",
    "                    intervals[counter] = [toBeRemoved[1], interval[1]]\n",
    "                    counter -= 1\n",
    "            elif interval[1] > toBeRemoved[1]:\n",
    "                res.append([toBeRemoved[1], interval[1]])\n",
    "            counter += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        left,right = toBeRemoved[0],toBeRemoved[1]\n",
    "        for interval in intervals:\n",
    "            if interval[1]<left or interval[0]>=right:\n",
    "                res.append(interval)\n",
    "            if interval[1] in range(left,right) and interval[0]<left:\n",
    "                res.append([interval[0],left])\n",
    "            if interval[0] in range(left+1,right) and interval[1]>=right:\n",
    "                res.append([right,interval[1]])\n",
    "            if interval[0]<=left and interval[1]>=right:\n",
    "                if interval[0]!=left:\n",
    "                    res.append([interval[0],left])\n",
    "                if interval[1]!=right:\n",
    "                    res.append([right,interval[1]])\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        minval = toBeRemoved[0]\n",
    "        maxval = toBeRemoved[1]\n",
    "        result = []\n",
    "        for interval in intervals:\n",
    "            if interval[1] <= minval or interval[0] >= maxval:\n",
    "                result.append(interval)\n",
    "            else:\n",
    "                if interval[0] < minval:\n",
    "                    result.append([interval[0],minval])\n",
    "                if interval[1] > maxval:\n",
    "                    result.append([maxval,interval[1]])\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        stack = []\n",
    "        for interval in intervals:\n",
    "            if interval[1] <= toBeRemoved[0] or interval[0] >= toBeRemoved[1]:\n",
    "                stack.append(interval)\n",
    "            elif interval[0] >= toBeRemoved[0] and interval[1] <= toBeRemoved[1]:\n",
    "                continue\n",
    "            elif interval[0] <= toBeRemoved[0] and interval[1] >= toBeRemoved[1]:\n",
    "                if interval[0] == toBeRemoved[0]:\n",
    "                    stack.append([toBeRemoved[1], interval[1]])\n",
    "                elif interval[1] == toBeRemoved[1]:\n",
    "                    stack.append([interval[0], toBeRemoved[0]])\n",
    "                else:\n",
    "                    stack.append([interval[0], toBeRemoved[0]])\n",
    "                    stack.append([toBeRemoved[1], interval[1]])\n",
    "            elif interval[0] > toBeRemoved[0]:\n",
    "                stack.append([toBeRemoved[1], interval[1]])\n",
    "            elif interval[1] < toBeRemoved[1]:\n",
    "                stack.append([interval[0], toBeRemoved[0]])\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        # 有序的 不相交\n",
    "\n",
    "        # 确定边界,和每一个的左右进行判断\n",
    "        # 每一边进行确定\n",
    " \n",
    "        res = []\n",
    "        for interval in intervals:\n",
    "            # if intervals[0][0]>toBeRemoved[0] and intervals[-1][1]<toBeRemoved[1]\n",
    "\n",
    "            # 没有交集\n",
    "            if interval[1]<toBeRemoved[0] or interval[0]>toBeRemoved[1]:\n",
    "                res.append(interval)\n",
    "            # 完全覆盖\n",
    "            elif interval[0]<toBeRemoved[0] and toBeRemoved[1]<interval[1]:\n",
    "                res.append([interval[0],toBeRemoved[0]])\n",
    "                res.append([toBeRemoved[1],interval[1]])\n",
    "\n",
    "            # 不需要判断另一侧，否则是完全覆盖的情况\n",
    "            # 左部分交集\n",
    "            elif interval[0]<toBeRemoved[0]:\n",
    "                res.append([interval[0],toBeRemoved[0]])\n",
    "\n",
    "            # 右部分交集\n",
    "            elif toBeRemoved[1]<interval[1]:\n",
    "                res.append([toBeRemoved[1],interval[1]])\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        lis=[]\n",
    "        mark,mark2,mark3,mark4=True,True,True,True\n",
    "        if intervals[0]==toBeRemoved:\n",
    "            return []\n",
    "        for i in intervals:\n",
    "            if toBeRemoved[0]<=i[1] and toBeRemoved[0]>=i[0]:\n",
    "                if i[0]!=toBeRemoved[0]:\n",
    "                    lis.append([i[0],toBeRemoved[0]])\n",
    "                    mark=False\n",
    "            if mark2:\n",
    "                if not toBeRemoved[0]>i[1]:\n",
    "                    mark=False\n",
    "                    mark2=False\n",
    "            if mark:    \n",
    "                lis.append(i)\n",
    "            if toBeRemoved[1]<=i[1] and toBeRemoved[1]>=i[0]:\n",
    "                if toBeRemoved[1]!=i[1]:\n",
    "                    lis.append([toBeRemoved[1],i[1]])\n",
    "                mark=True\n",
    "                mark4=False\n",
    "            if mark3:\n",
    "                if not toBeRemoved[1]>i[0] and mark4:\n",
    "                    lis.append(i)\n",
    "                    mark=True\n",
    "                    mark3=False\n",
    "        return lis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        lis,mark=[],True\n",
    "        mark2,mark3,mark4=True,True,True\n",
    "        if intervals[0]==toBeRemoved:\n",
    "            return []\n",
    "        for i in intervals:\n",
    "            if toBeRemoved[0]<=i[1] and toBeRemoved[0]>=i[0]:\n",
    "                if i[0]!=toBeRemoved[0]:\n",
    "                    lis.append([i[0],toBeRemoved[0]])\n",
    "                    mark=False\n",
    "            if mark2:\n",
    "                if not toBeRemoved[0]>i[1]:\n",
    "                    mark=False\n",
    "                    mark2=False\n",
    "            if mark:    \n",
    "                lis.append(i)\n",
    "            if toBeRemoved[1]<=i[1] and toBeRemoved[1]>=i[0]:\n",
    "                if toBeRemoved[1]!=i[1]:\n",
    "                    lis.append([toBeRemoved[1],i[1]])\n",
    "                mark=True\n",
    "                mark4=False\n",
    "            if mark3:\n",
    "                if not toBeRemoved[1]>i[0] and mark4:\n",
    "                    lis.append(i)\n",
    "                    mark=True\n",
    "                    mark3=False\n",
    "        return lis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        lis=[]\n",
    "        for i in intervals:\n",
    "            if i[1]<=toBeRemoved[0] or i[0]>=toBeRemoved[1]:\n",
    "                lis.append(i)   \n",
    "            else:\n",
    "                if i[0]<toBeRemoved[0]:\n",
    "                    lis.append([i[0],toBeRemoved[0]])\n",
    "                if i[1]>toBeRemoved[1]:\n",
    "                    lis.append([toBeRemoved[1],i[1]])\n",
    "        return lis\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for interval in intervals:\n",
    "            # 不相交\n",
    "            if toBeRemoved[1] < interval[0] or toBeRemoved[0] >= interval[1]:\n",
    "                ans.append(interval)\n",
    "                continue\n",
    "            # 相交\n",
    "            if interval[0] < toBeRemoved[0]:\n",
    "                ans.append([interval[0], toBeRemoved[0]])\n",
    "            if interval[1] > toBeRemoved[1]:\n",
    "                ans.append([toBeRemoved[1], interval[1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param intervals:\n",
    "        :param toBeRemoved:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        res = []\n",
    "        for interval in intervals:\n",
    "            if interval[1] <= toBeRemoved[0] or interval[0] >= toBeRemoved[1]:\n",
    "                res.append(interval)\n",
    "            else:\n",
    "                if interval[0] < toBeRemoved[0]:\n",
    "                    res.append([interval[0], toBeRemoved[0]])\n",
    "                if interval[1] > toBeRemoved[1]:\n",
    "                    res.append([toBeRemoved[1], interval[1]])\n",
    "        return res\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.removeInterval(intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        anw = []\n",
    "        for inter in intervals:\n",
    "            if inter[1] <= toBeRemoved[0] or inter[0] >= toBeRemoved[1]:\n",
    "                anw.append(inter)\n",
    "            elif inter[0] < toBeRemoved[0] and toBeRemoved[0] <= inter[1] and toBeRemoved[1] >= inter[1]:\n",
    "                anw.append([inter[0], toBeRemoved[0]])\n",
    "            elif toBeRemoved[1] >= inter[0] and toBeRemoved[1] < inter[1] and toBeRemoved[0] <= inter[0]:\n",
    "                anw.append([toBeRemoved[1], inter[1]])\n",
    "            elif toBeRemoved[1] < inter[1] and toBeRemoved[0] > inter[0]:\n",
    "                anw.append([inter[0], toBeRemoved[0]])\n",
    "                anw.append([toBeRemoved[1], inter[1]])\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "        return anw \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        n = len(intervals)\n",
    "        intervals.sort()\n",
    "        res = []\n",
    "        for x in intervals:\n",
    "            if x[1] <= toBeRemoved[0]:\n",
    "                res.append(x)\n",
    "            elif x[0] >= toBeRemoved[1]:\n",
    "                res.append(x)\n",
    "            else:\n",
    "                if toBeRemoved[0] <= x[0] and x[1] <= toBeRemoved[1]:\n",
    "                    continue\n",
    "                elif x[0] <= toBeRemoved[0] and x[1] <= toBeRemoved[1]:\n",
    "                    res.append([x[0], toBeRemoved[0]])\n",
    "                elif toBeRemoved[0] <= x[0] and toBeRemoved[1] <= x[1]:\n",
    "                    res.append([toBeRemoved[1], x[1]])\n",
    "                else:\n",
    "                    res.append([x[0], toBeRemoved[0]])\n",
    "                    res.append([toBeRemoved[1], x[1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        output = []\n",
    "        for interval in intervals:\n",
    "            if interval[1] <= toBeRemoved[0]:\n",
    "                output.append(interval)\n",
    "            else:\n",
    "                if interval[1] > toBeRemoved[1] and interval[0] < toBeRemoved[0]:\n",
    "                    output.append([interval[0], toBeRemoved[0]])\n",
    "                    output.append([toBeRemoved[1], interval[1]])\n",
    "                elif interval[1] <= toBeRemoved[1] and interval[0] < toBeRemoved[0]:\n",
    "                    output.append([interval[0], toBeRemoved[0]])\n",
    "                elif interval[0] >= toBeRemoved[1]:\n",
    "                    output.append(interval)\n",
    "                elif interval[0] >= toBeRemoved[0] and interval[1] > toBeRemoved[1]:\n",
    "                    output.append([toBeRemoved[1], interval[1]])\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        ret = []\n",
    "        for it in intervals:\n",
    "            st, ed = it\n",
    "            if ed < toBeRemoved[0]:\n",
    "                ret.append(it)\n",
    "            elif st > toBeRemoved[1]:\n",
    "                ret.append(it)\n",
    "            elif st >= toBeRemoved[0] and ed <= toBeRemoved[1]:\n",
    "                continue\n",
    "            elif st <= toBeRemoved[0] and ed >= toBeRemoved[1]:\n",
    "                ret.extend(\n",
    "                    [[st, toBeRemoved[0]], [toBeRemoved[1], ed]]\n",
    "                )\n",
    "            elif st <= toBeRemoved[0] and ed  >= toBeRemoved[0]:\n",
    "                ret.append([st, toBeRemoved\n",
    "                [0]])\n",
    "            elif st <= toBeRemoved[1] and ed >= toBeRemoved[1]:\n",
    "                ret.append([toBeRemoved[1], ed])\n",
    "        return [_ for _ in ret if _[1] - _[0] >= 1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        stack = []\n",
    "        for interval in intervals:\n",
    "            if interval[1] <= toBeRemoved[0] or interval[0] >= toBeRemoved[1]:\n",
    "                stack.append(interval)\n",
    "            else:\n",
    "                if interval[0] < toBeRemoved[0]:\n",
    "                    stack.append([interval[0], toBeRemoved[0]])\n",
    "                if interval[1] > toBeRemoved[1]:\n",
    "                    stack.append([toBeRemoved[1], interval[1]])\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for interval in intervals:\n",
    "            if interval[0] > toBeRemoved[1] or interval[1] < toBeRemoved[0]:\n",
    "                res.append(interval)\n",
    "            else:\n",
    "                if interval[0] < toBeRemoved[0]:\n",
    "                    res.append([interval[0], toBeRemoved[0]]) \n",
    "                if interval[1] > toBeRemoved[1]:\n",
    "                    res.append([toBeRemoved[1], interval[1]])           \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i in intervals:\n",
    "            if i[1] < toBeRemoved[0] or i[0] > toBeRemoved[1]:\n",
    "                res.append(i)\n",
    "            else:\n",
    "                if i[0] < toBeRemoved[0]:\n",
    "                    res.append([i[0], toBeRemoved[0]])\n",
    "                if i[1] > toBeRemoved[1]:\n",
    "                    res.append([toBeRemoved[1], i[1]])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "\n",
    "        for start, end in intervals:\n",
    "            # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                # 需要保留左区间, 屁股被吃了\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                # 需要保留右区间， 头被吃了\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "\n",
    "        return output\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "\n",
    "        for start, end in intervals:\n",
    "            # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                # 需要保留左区间吗？\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                # 需要保留右区间吗？\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        cur=0\n",
    "        res=[]\n",
    "        n=len(intervals)\n",
    "        l,r=toBeRemoved\n",
    "        for x,y in intervals:\n",
    "            if y<=l or x>=r:\n",
    "                res.append((x,y))\n",
    "            elif x<l and y<=r:\n",
    "                res.append((x,l))\n",
    "            elif x>=l and y>r:\n",
    "                res.append((r,y))\n",
    "            elif x<l and y>r:\n",
    "                res.append((x,l))\n",
    "                res.append((r,y))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        remove_start,remove_end = toBeRemoved\n",
    "        output = []\n",
    "        for start,end in intervals:\n",
    "            #没有重叠，原样添加\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start,end])\n",
    "            else:\n",
    "                #需要保留左？\n",
    "                if start < remove_start:\n",
    "                    output.append([start,remove_start])\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end,end])\n",
    "        return output\n",
    "        # remove_start, remove_end = toBeRemoved\n",
    "        # output = []\n",
    "\n",
    "        # for start, end in intervals:\n",
    "        #     # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "        #     if start > remove_end or end < remove_start:\n",
    "        #         output.append([start, end])\n",
    "        #     else:\n",
    "        #         # 需要保留左区间吗？\n",
    "        #         if start < remove_start:\n",
    "        #             output.append([start, remove_start])\n",
    "        #         # 需要保留右区间吗？\n",
    "        #         if end > remove_end:\n",
    "        #             output.append([remove_end, end])\n",
    "\n",
    "        # return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        for s, e in intervals:\n",
    "            if toBeRemoved[0] <= s < toBeRemoved[1]:\n",
    "                s = toBeRemoved[1]\n",
    "            elif toBeRemoved[0] < e <= toBeRemoved[1]:\n",
    "                e = toBeRemoved[0]\n",
    "            elif s < toBeRemoved[0] < toBeRemoved[1] < e:\n",
    "                res.append([s, toBeRemoved[0]])\n",
    "                res.append([toBeRemoved[1], e])\n",
    "                s = e + 1\n",
    "\n",
    "            if s < e:\n",
    "                res.append([s, e])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        l, r = toBeRemoved\n",
    "        res = []\n",
    "        for s,e in intervals:\n",
    "            if e <= l or s >= r:\n",
    "                res.append([s,e])\n",
    "            else:\n",
    "                if s < l:\n",
    "                    res.append([s,l])\n",
    "                if e > r:\n",
    "                    res.append([r,e])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "\n",
    "        ret = []\n",
    "        lower, upper = toBeRemoved\n",
    "        for start, end in intervals:\n",
    "            if end <= lower or start >= upper:\n",
    "                ret.append([start, end])\n",
    "                continue\n",
    "            # 两段的区间分别考虑，无需组合\n",
    "            if lower > start:\n",
    "                ret.append([start, lower])\n",
    "            if upper < end:\n",
    "                ret.append([upper, end])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "\n",
    "        result = []\n",
    "        for start, end in intervals:\n",
    "            if start > remove_end or end < remove_start:\n",
    "                result.append([start, end])\n",
    "            else:\n",
    "                if start < remove_start:\n",
    "                    result.append([start, remove_start])\n",
    "                if end > remove_end:\n",
    "                    result.append([remove_end, end])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "\n",
    "        for start, end in intervals:\n",
    "            # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "            if start >= remove_end or end <= remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                # 需要保留左区间吗？\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                # 需要保留右区间吗？\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "\n",
    "        for start, end in intervals:\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        start, end = toBeRemoved\n",
    "        res = []\n",
    "        for s, e in intervals:\n",
    "            if s >= end or e <= start:\n",
    "                res.append([s, e])\n",
    "            else:\n",
    "                if s < start:\n",
    "                    res.append([s, start])\n",
    "                if e > end:\n",
    "                    res.append([end, e])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        line=[]\n",
    "        for i in intervals:\n",
    "            i_left=i[0]\n",
    "            i_right=i[1]\n",
    "            j=toBeRemoved\n",
    "            j_left=j[0]\n",
    "            j_right=j[1]\n",
    "\n",
    "            if i_left<j_left:\n",
    "                if i_right<=j_left:\n",
    "                    line.append([i_left,i_right])\n",
    "                elif i_right<=j_right:\n",
    "                    line.append([i_left,j_left])\n",
    "                else:\n",
    "                    line.append([i_left,j_left])\n",
    "                    line.append([j_right,i_right])\n",
    "            elif i_left>=j_left and i_left<j_right:\n",
    "                if i_right>j_right:\n",
    "                    line.append([j_right,i_right])\n",
    "            else:\n",
    "                line.append([i_left,i_right])\n",
    "        return line\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for start, end in intervals:\n",
    "            l, r = toBeRemoved\n",
    "            if end <= l or start >= r:\n",
    "                ans.append([start, end])\n",
    "            else:\n",
    "                if start < l:\n",
    "                    ans.append([start, l])\n",
    "                    if end > r:\n",
    "                        ans.append([r, end])\n",
    "                elif end > r:\n",
    "                    ans.append([r, end])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        a, b = toBeRemoved\n",
    "        intervals.sort()\n",
    "        ans = []\n",
    "        for x, y in intervals:\n",
    "            if y <= a:\n",
    "                ans.append([x, y])\n",
    "            elif x >= b:\n",
    "                ans.append([x, y])\n",
    "            else:\n",
    "                low = max(x, a)\n",
    "                high = min(y, b)\n",
    "                if x < low:\n",
    "                    ans.append([x, low])\n",
    "                if high < y:\n",
    "                    ans.append([high, y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "\n",
    "        for start, end in intervals:\n",
    "            # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                # 需要保留左区间吗？\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                # 需要保留右区间吗？\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        left, right = toBeRemoved\n",
    "        ans = []\n",
    "        for li, ri in intervals:\n",
    "            if li > right or ri < left:\n",
    "                ans.append([li, ri])\n",
    "            else:\n",
    "                if li < left:\n",
    "                    ans.append([li, left])\n",
    "                if ri > right:\n",
    "                    ans.append([right, ri])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "        for start, end in intervals:\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        re_s, re_e = toBeRemoved\n",
    "        for start, end in intervals:\n",
    "            new_start = min(start, re_s)\n",
    "            new_end = max(re_e, end)\n",
    "            if new_start < re_s:\n",
    "                ans.append([new_start, min(re_s, end)])\n",
    "            if new_end > re_e:\n",
    "                ans.append([max(re_e, start), new_end])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        intervals.sort()\n",
    "        result = list()\n",
    "        rx, ry = toBeRemoved[0], toBeRemoved[1]\n",
    "        for it in intervals:\n",
    "            x, y = it[0], it[1]\n",
    "            if y <= rx:\n",
    "                result.append([x, y])\n",
    "            elif y <= ry:\n",
    "                if x < rx:\n",
    "                    result.append([x, rx])\n",
    "            else:\n",
    "                if x < rx:\n",
    "                    result.append([x, rx])\n",
    "                    result.append([ry, y])\n",
    "                elif x < ry:\n",
    "                    result.append([ry, y])\n",
    "                else:\n",
    "                    result.append([x, y])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        left, right = toBeRemoved[0], toBeRemoved[1]\n",
    "        res = []\n",
    "        for i in intervals:\n",
    "            if left > i[0]:\n",
    "                res.append([i[0], min(i[1], left)])   \n",
    "            if right < i[1]:\n",
    "                res.append([max(i[0], right), i[1]])\n",
    "                       \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        # res = []\n",
    "        # for interval in intervals:\n",
    "        #     if interval[1] <= toBeRemoved[0] or interval[0] >= toBeRemoved[1]:\n",
    "        #         res.append(interval)\n",
    "        #     elif interval[0] < toBeRemoved[0]:\n",
    "        #         if interval[1] > toBeRemoved[1]:\n",
    "        #             res.append([interval[0], toBeRemoved[0]])\n",
    "        #             res.append([toBeRemoved[1], interval[1]])\n",
    "        #         elif interval[1] <= toBeRemoved[0]:\n",
    "        #             res.append(interval)\n",
    "        #         else:\n",
    "        #             res.append([interval[0], toBeRemoved[0]])\n",
    "        #     elif interval[0] == toBeRemoved[0]:\n",
    "        #         if interval[1] > toBeRemoved[1]:\n",
    "        #             res.append([toBeRemoved[1], interval[1]])\n",
    "        #     else:\n",
    "        #         if interval[1] <= toBeRemoved[1]:\n",
    "        #             continue\n",
    "        #         else:\n",
    "        #             res.append([toBeRemoved[1], interval[1]])\n",
    "        # return res\n",
    "\n",
    "\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "\n",
    "        for start, end in intervals:\n",
    "            # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                # 需要保留左区间吗？\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                # 需要保留右区间吗？\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "\n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 扫描线算法\n",
    "    def removeInterval1(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "\n",
    "        for start, end in intervals:\n",
    "            # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                # 需要保留左区间吗？\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                # 需要保留右区间吗？\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "\n",
    "        return output\n",
    "\n",
    "\n",
    "\n",
    "    # ^\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        for s, e in intervals:\n",
    "            if toBeRemoved[0] <= s < toBeRemoved[1]:\n",
    "                s = toBeRemoved[1]\n",
    "            elif toBeRemoved[0] < e <= toBeRemoved[1]:\n",
    "                e = toBeRemoved[0]\n",
    "            elif s < toBeRemoved[0] < toBeRemoved[1] < e:\n",
    "                res.append([s, toBeRemoved[0]])\n",
    "                res.append([toBeRemoved[1], e])\n",
    "                s = e + 1\n",
    "\n",
    "            if s < e:\n",
    "                res.append([s, e])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        [L, R] = toBeRemoved\n",
    "        res = []\n",
    "        for l, r in intervals:\n",
    "            if l >= R or r <= L:\n",
    "                res.append([l, r])\n",
    "            else:\n",
    "                if l < L:\n",
    "                    res.append([l, L])\n",
    "                if r > R:\n",
    "                    res.append([R, r])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "\n",
    "        ret = []\n",
    "        lower, upper = toBeRemoved\n",
    "        for start, end in intervals:\n",
    "            if end <= lower or start >= upper:\n",
    "                ret.append([start, end])\n",
    "                continue\n",
    "            if lower <= start and upper >= end:\n",
    "                continue\n",
    "            if lower <= start:\n",
    "                ret.append([upper, end])\n",
    "            elif upper >= end:\n",
    "                ret.append([start, lower])\n",
    "            else:\n",
    "                ret.extend([[start, lower], [upper, end]])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        low, high = toBeRemoved\n",
    "        for a, b in intervals:\n",
    "            if b <= low or a >= high:\n",
    "                ans.append([a, b])\n",
    "            else:\n",
    "                if a < low:\n",
    "                    ans.append([a, low])\n",
    "                if b > high:\n",
    "                    ans.append([high, b])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for start, end in intervals:\n",
    "            l, r = toBeRemoved\n",
    "            # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "            if end <= l or start >= r:\n",
    "                ans.append([start, end])\n",
    "            else:\n",
    "                # 需要保留左区间吗？\n",
    "                if start < l:\n",
    "                    ans.append([start, l])\n",
    "                # 需要保留右区间吗？\n",
    "                if end > r:\n",
    "                    ans.append([r, end])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        rmvleft, rmvright = toBeRemoved[0], toBeRemoved[1]\n",
    "        output = []\n",
    "        for l, r in intervals:\n",
    "            if r<=rmvleft or l>=rmvright:\n",
    "                output.append([l, r])\n",
    "            else:\n",
    "                if l<rmvleft:\n",
    "                    output.append([l, rmvleft])\n",
    "                if r>rmvright:\n",
    "                    output.append([rmvright, r])\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "        # intervals = sorted(intervals, key=lambda x: x[0])\n",
    "        ans = []\n",
    "        for inter in intervals:\n",
    "            if inter[0] < toBeRemoved[0] and inter[1] > toBeRemoved[1]:\n",
    "                ans.append([inter[0], toBeRemoved[0]])\n",
    "                ans.append([toBeRemoved[1], inter[1]])\n",
    "            elif inter[0] < toBeRemoved[0]:\n",
    "                ans.append([inter[0], min(inter[1], toBeRemoved[0])])\n",
    "            elif inter[0] >= toBeRemoved[0] and inter[1] > toBeRemoved[1]:\n",
    "                ans.append([max(inter[0], toBeRemoved[1]), inter[1]])\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:\n",
    "\n",
    "        remove_start, remove_end = toBeRemoved\n",
    "        output = []\n",
    "\n",
    "        for start, end in intervals:\n",
    "            # 如果没有重叠，则按原样将间隔添加到列表中。\n",
    "            if start > remove_end or end < remove_start:\n",
    "                output.append([start, end])\n",
    "            else:\n",
    "                # 需要保留左区间吗？\n",
    "                if start < remove_start:\n",
    "                    output.append([start, remove_start])\n",
    "                # 需要保留右区间吗？\n",
    "                if end > remove_end:\n",
    "                    output.append([remove_end, end])\n",
    "\n",
    "        return output\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
